package leetcode.tree_problem;

/**
 * 543. 二叉树的直径
 * https://leetcode-cn.com/problems/diameter-of-binary-tree/
 */
public class 二叉树的直径 {
    public int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)){
            return 0;
        }
        height(root);
        return max;
    }
    public int height(TreeNode root){//求二叉树每个节点的高度，注意语义
        if (root == null){
            return 0;
        }

        //分别求出左右子树的高度
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        max = Math.max(max , leftHeight + rightHeight);//确定最大高度以确定直经，即每个节点的左右子树的高度和看那个节点1的高做记录
        return 1 + Math.max(leftHeight , rightHeight);//返回节点的最大高，即左右子树哪边高
    }
}
